package com.example.lettcode._20241012;

import java.sql.Array;
import java.util.*;

/*
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]
 */
public class Zi_mu_yi_wei_ci_fen_zu {

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        for (List<String> list : groupAnagrams(strs)) {
            list.forEach(System.out::print);
            System.out.println();
        }
    }

    /*
    暴力处理
        1、遍历数组，对每个字符排序
        2、统计相同的字符的索引
        3、将相同索引的数据存放与list中
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<Integer>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);
            if (map.containsKey(s)) {
                map.get(s).add(i);
                continue;
            }
            List<Integer> list = new ArrayList<>();
            list.add(i);
            map.put(s, list);
        }

       List<List<String>> list = new ArrayList<>();
       for (List<Integer> list1 : map.values()) {
           List<String> list3 = new ArrayList<>();
           for (int i = 0; i < list1.size(); i++) {
               Integer integer = list1.get(i);
               list3.add(strs[integer]);
           }
           list.add(list3);
       }
       return list;
    }


    /*
   暴力处理
       1、遍历数组，对每个字符排序
       2、统计相同的字符的索引
       3、将相同索引的数据存放与list中
    优化：
        并不需要统计相同字符的索引，直接将对应位置的字符串存放进集合即可
    */
    public static List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);
            if (map.containsKey(s)) {
                map.get(s).add(str);
                continue;
            }
            List<String> list = new ArrayList<>();
            list.add(str);
            map.put(s, list);
        }
        return new ArrayList<>(map.values());
    }
}
